In digital communications and signal processing applications, continuous physical phenomena, or signals, such as electromagnetic waves, are used for encoding digital information. Recovery of the digital signal encoded in the continuous physical signal consists in sampling the continuous signal at some sampling rate. Conventional sampling methods typically require a sampling rate of at least twice the maximum frequency in the continuous signal, also known as the Nyquist sampling rate, for reliable digital signal reconstruction. In many applications, however, processing cost is related to the sampling rate, and it is therefore desirable to develop techniques which enable reduction of the measurement sampling rate.
Recovery of a digital signal by sampling an encoded continuous signal at sub-Nyquist sampling rates is possible if it is known or expected that the digital signal is sparse, meaning that many of the coefficients of the signal are equal to zero or nearly so. This technique is known as compressed sensing. The assumption of sparsity is an additional constraint which may enable a solution to the problem.
Recovering a sparse signal from an underdetermined set of observations is a Non-deterministic Polynomial-time hard (NP-hard) problem, but may be rendered a convex optimization problem if an l1 norm is used as the sparsifying norm. A number of algorithms for solving this optimization problem have been proposed. Some known algorithms employ the least absolute shrinkage and selection operator (“Lasso”) version of the least squares method. Two such known algorithms include least-angle regression (LARS) and coordinate descent (CD). These algorithms suffer from certain limitations, however. Firstly, they do not solve the original compressed sensing problem because it is NP-hard. Secondly, because of their sensitivity to certain parameters, they do not necessarily find an optimum solution to the problem after a given number of iterations. In addition, known iterative compressed sensing algorithms tend to increase in complexity with each iteration thus adding processing cost to the attainment of increasingly better estimates of the digital signal elements.
It remains desirable, therefore, to develop improved techniques for recovery of sparse signals using compressed sensing algorithms having lower complexity and processing cost.